<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Simple User-defined Constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial058.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial060.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc121">8.6</A>&nbsp;&nbsp;Simple User-defined Constraints</H2><UL>
<LI><A HREF="tutorial059.html#toc64">Using Reified Constraints</A>
<LI><A HREF="tutorial059.html#toc65">Using Propia</A>
<LI><A HREF="tutorial059.html#toc66">Using the <EM>element</EM> Constraint</A>
</UL>

User-defined, or `conceptual' constraints can easily be defined as 
conjunctions of primitive constraints. For example, let us consider a set 
of products and the specification that allows them to be colocated in a 
warehouse. This should be done in such a way as to propagate possible 
changes in the domains as soon as this becomes possible. <BR>
<BR>
Let us assume we have a symmetric relation that defines which product
can be colocated with another and that products are distinguished by numeric 
product identifiers: <BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
colocate(100, 101).
colocate(100, 102).
colocate(101, 100).
colocate(102, 100).
colocate(103, 104).
colocate(104, 103).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Suppose we define a constraint <CODE>colocate_product_pair(X, Y)</CODE> such 
that any change of the possible values of <I>X</I> or <I>Y</I> is propagated to the 
other variable. There are many ways in which this pairing 
can be defined in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>. They are different solutions with different
properties, but they yield the same results.<BR>
<BR>
<A NAME="toc64"></A>
<H3 CLASS="subsection"><A NAME="htoc122">8.6.1</A>&nbsp;&nbsp;Using Reified Constraints</H3>
We can encode directly the relations between elements in the
domains of the two variables: 

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
colocate_product_pair(A, B) :-
    cpp(A, B),
    cpp(B, A).

cpp(A, B) :-
    [A,B] :: [100, 101, 102, 103, 104],
    A #= 100 =&gt; B :: [101, 102],
    A #= 101 =&gt; B #= 100,
    A #= 102 =&gt; B #= 100,
    A #= 103 =&gt; B #= 104,
    A #= 104 =&gt; B #= 103.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
This method is quite simple and does not need any special analysis; on
the other hand it potentially creates a huge number of auxiliary
constraints and variables. <BR>
<BR>
<A NAME="toc65"></A>
<H3 CLASS="subsection"><A NAME="htoc123">8.6.2</A>&nbsp;&nbsp;Using Propia</H3>
By far the simplest mechanism, that avoids this potential creation of large
numbers of auxiliary constraints and variables, is to load the Generalised 
Propagation library (<EM>propia</EM>) and use arc-consistency (<EM>ac</EM>) 
propagation, viz:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- colocate(X,Y) infers ac
</PRE></BLOCKQUOTE>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">Additional information on <EM>propia</EM> can be found in 
section&nbsp;</FONT><A HREF="tutorial110.html#secpropia"><FONT COLOR="#9832CC">15.3</FONT></A><FONT COLOR="#9832CC">, section&nbsp;</FONT><A HREF="tutorial107.html#chappropiachr"><FONT COLOR="#9832CC">15</FONT></A><FONT COLOR="#9832CC"> and the ECL</FONT><SUP><FONT COLOR="#9832CC"><I>i</I></FONT></SUP><FONT COLOR="#9832CC">PS</FONT><SUP><FONT COLOR="#9832CC"><I>e</I></FONT></SUP><FONT COLOR="#9832CC"> Constraint
Library Manual.</FONT>
</DL>

<A NAME="toc66"></A>
<H3 CLASS="subsection"><A NAME="htoc124">8.6.3</A>&nbsp;&nbsp;Using the <EM>element</EM> Constraint</H3> 
<A NAME="icelement"></A>
In this case we use the <CODE>element/3</CODE> predicate,
that states in a list of integers that the element at
an index is equal to a value. Every time the index or the value is updated,
the constraint is activated and the domain of the other variable is updated
accordingly.<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
relates(X, Xs, Y, Ys) :-
    element(I, Xs, X),
    element(I, Ys, Y).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
We define a generic predicate, <CODE>relates/4</CODE>, that associates the
corresponding elements at a specific index of two lists, with one 
another. The variable <I>I</I> is an index into the lists, 
<I>Xs</I> and <I>Ys</I>, to yield the elements at this index, 
in variables <I>X</I> and <I>Y</I>.<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
colocate_product_pair(A, B) :-
    relates(A, [100, 100, 101, 102, 103, 104], 
            B, [101, 102, 100, 100, 104, 103]).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The <CODE>colocate_product_pair</CODE> predicate simply calls <CODE>relates/4</CODE>
passing a list containing the product identifiers in the first argument 
of <CODE>colocate/2</CODE> as <I>Xs</I> and a list containing product identifiers 
from the second argument of <CODE>colocate/2</CODE> as <I>Ys</I>.<BR>
<BR>
Behind the scenes, this is exactly the implementation used for
arc-consistency propagation by the Generalised Propagation library.<BR>
<BR>
Because of the specific and efficient algorithm implementing the
<CODE>element/3</CODE> constraint, it is usually faster than the first
approach, using reified constraints. <BR>
<BR>
<HR>
<A HREF="tutorial058.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial060.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
